package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list'>从链表中删去总和值为零的连续节点(Remove Zero Sum Consecutive Nodes from Linked List)</a>
 * <p>给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。</p>
 * <p>删除完毕后，请你返回最终结果链表的头节点。</p>
 * <p>你可以返回任何满足题目要求的答案。(（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）)</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：head = [1,2,-3,3,1]
 *      输出：[3,1]
 *      提示：答案 [1,2,1] 也是正确的。
 *
 * 示例 2：
 *      输入：head = [1,2,3,-3,4]
 *      输出：[1,2,4]
 *
 * 示例 3：
 *      输入：head = [1,2,3,-3,-2]
 *      输出：[1]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>给你的链表中可能有 1 到 1000 个节点。</li>
 *     <li>对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/8 16:56
 */
public class LC1171RemoveZeroSumConsecutiveNodesFromLinkedList_M {
    static class Solution {
        public ListNode removeZeroSumSublists(ListNode head) {
            if (head == null) {
                return null;
            }
            // 以head作为开头，是否存在一段以 head 开头的和为 0 的连续节点，如果存在的话，删去这段节点
            int sum = 0;
            ListNode currNode = head;
            while (currNode != null) {
                sum += currNode.val;
                if (sum == 0) {
                    return removeZeroSumSublists(currNode.next);
                }
                currNode = currNode.next;
            }
            // 能到达这里说明不存在从 head 开始的一段和为0的连续节点，继续判断是否存在以 head.next 开始的一段和为0的连续节点
            head.next = removeZeroSumSublists(head.next);
            return head;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.removeZeroSumSublists(Generator.create(1, 2, -3, 3, 1)));
        Printer.printListNode(solution.removeZeroSumSublists(Generator.create(1, 2, 3, -3, 4)));
        Printer.printListNode(solution.removeZeroSumSublists(Generator.create(1, 2, 3, -3, -2)));
    }
}